#include<vector>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:

    int coinChange(vector<int>& coins, int amount) {
        unordered_map<int, int> memo;

        return dp(coins, amount, memo);
    }

    // 总额 n最少需要几个硬币
    int dp(vector<int>& coins, int n, unordered_map<int, int> memo){
        // cout << "n, memo.count(n): " << n<<","<<memo.count(n)<<endl; 
        if (memo.count(n) == 1) {
            cout<<"n="<<n<<endl;
            return memo[n];
        }
        // base case
        if(n == 0) return 0;
        if(n < 0) return -1;
        int ret = INT_MAX;

        for (int coin : coins){
            int sub_problem = dp(coins, n - coin, memo);
            if (sub_problem == -1) continue;
            ret = min(ret, sub_problem + 1);
            
            // cout << "n, coin, ret: " << n << "," << coin <<","<< ret << endl;
        }

        memo[n] = ret == INT_MAX ? -1 : ret;
        if(memo.count(n) == 1) cout << "memo n exists:"<<n<<" memo[n]="<<memo[n]<<endl;
        return memo[n];
    }
};

int main(){
    Solution slu;
    vector<int> coins = {1, 2, 5};
    int ret = slu.coinChange(coins, 30);

    cout << ret << endl;

    return 0;
}